English+GermanWikipedia - /page/entry.mu

Micron Document

<!DOCTYPE html>

<title>Prozess-Scheduler</title>

</head>

<h1 id="firstHeading" class="firstHeading mw-first-heading"><span class="mw-page-title-main">Prozess-Scheduler</span></h1>

</header>

</div>

<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="de" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="de" dir="ltr"><p>Ein <b>Prozess-Scheduler</b> (Scheduler = Steuerprogramm; vom englischen <i><span lang="en">schedule</span></i> für „Zeitplan“) ist eine <a href="Arbiter" title="Arbiter">Arbitrations</a>logik, die die <a href="Scheduling" title="Scheduling">zeitliche Ausführung</a> mehrerer <a href="Prozess_(Informatik)" title="Prozess (Informatik)">Prozesse</a> in <a href="Betriebssystem" title="Betriebssystem">Betriebssystemen</a> und der <a href="Anwendungsvirtualisierung" title="Anwendungsvirtualisierung">Anwendungsvirtualisierung</a> regelt.

</p><p>Prozess-Scheduler lassen sich grob aufteilen in:

</p>

<ul><li><i>unterbrechende</i> (<i>präemptive</i>) Scheduler: sie teilen die CPU von vornherein nur für eine bestimmte Zeitspanne zu und entziehen sie dem Prozess daraufhin wieder.</li>

<li><i>nicht unterbrechende</i> Scheduler (<span lang="en"><i>non preemptive</i></span>, auch <i>kooperative</i> genannt): sie lassen einen Prozess, nachdem ihm die <a href="Central_Processing_Unit" class="mw-redirect" title="Central Processing Unit">CPU</a> einmal zugeteilt wurde, solange laufen, bis er die CPU von sich aus wieder freigibt oder bis er blockiert.</li></ul>

<p>Eine weitere mögliche Unterscheidung ist diejenige in:

</p>

<ul><li><i>work-conserving</i>-Strategien: das Umschalten zwischen Prozessen nimmt nur eine vernachlässigbar geringe Zeit in Anspruch.<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup></li>

<li><i>non work-conserving</i>-Strategien.</li></ul>

<p>Man kann verschiedene Systeme unterscheiden, in welchen jeweils verschiedene Anforderungen an den Scheduler gestellt werden:

</p>

<ol><li><a href="Stapelverarbeitung" title="Stapelverarbeitung">Stapelverarbeitungssysteme</a>: hier sieht der Scheduler denkbar einfach aus: ankommende Aufträge werden in eine <a href="Warteschlange_(Datenstruktur)" title="Warteschlange (Datenstruktur)">Warteschlange</a> eingereiht und jedes Mal, wenn ein Job abgearbeitet ist, kommt der nächste aus der Schlange dran (Queue-Manager).</li>

<li><a href="Mensch-Computer-Interaktion" title="Mensch-Computer-Interaktion">interaktive Systeme</a>: der Benutzer legt Wert auf kurze <a href="Antwortzeit" title="Antwortzeit">Antwortzeit</a>. Wenn er beispielsweise in einem <a href="Texteditor" title="Texteditor">Texteditor</a> eine Tastatureingabe tätigt, sollte der Text <i>sofort</i> erscheinen.</li>

<li><a href="Echtzeitbetriebssystem" title="Echtzeitbetriebssystem">Echtzeitsysteme</a>: sie müssen garantieren, dass ein Prozess eine Aufgabe innerhalb einer vorgegebenen Zeitspanne abgearbeitet haben muss. Bei harten Echtzeitanforderungen wird das in 100 % aller Fälle garantiert, während bei weichen Anforderungen das Zeitlimit in einigen wenigen Fällen überschritten werden darf.</li></ol>

<p>Typische <a href="Desktop-PC" class="mw-redirect" title="Desktop-PC">Desktop-PCs</a> sind interaktive Systeme, auf denen gelegentlich auch Prozesse als <a href="Hintergrundprozess" title="Hintergrundprozess">Hintergrundprozesse</a> mit niedrigerer <a href="Priorit%C3%A4t" title="Priorität">Priorität</a> ablaufen können.

</p>

<div class="mw-heading mw-heading2"><h2 id="Ziele">Ziele</h2></div>

<p>Die Zuteilung der CPU an die Prozesse sollte bestmöglich erfolgen, wobei (abhängig vom ausführenden System) unterschiedliche Ziele verfolgt werden können:

</p>

<div class="mw-heading mw-heading3"><h3 id="Allgemein">Allgemein</h3></div>

<ul><li>Fairness: Kein Prozess sollte unverhältnismäßig lange warten müssen, während ein anderer bevorzugt wird.</li>

<li>Balance: Die Prozesse sollten der CPU auf eine Weise zugeteilt werden, dass auch andere Ressourcen wie <a href="Massenspeicher" title="Massenspeicher">Massenspeicher</a>, <a href="Rechnernetz" title="Rechnernetz">Netzwerk</a>-Schnittstelle u. a. ausgelastet sind.</li>

<li>Einhaltung der Systemregeln.</li></ul>

<div class="mw-heading mw-heading3"><h3 id="Stapelverarbeitungssysteme">Stapelverarbeitungssysteme</h3></div>

<ul><li>CPU-<a href="Auslastung" class="mw-redirect" title="Auslastung">Auslastung</a>: Die CPU sollte zu jeder Zeit ausgelastet sein. Es soll nicht vorkommen, dass die CPU sich im <a href="Leerlauf" title="Leerlauf">Leerlauf</a> befindet, nur weil ein Prozess auf Daten von der <a href="Festplatte" title="Festplatte">Festplatte</a> wartet.</li>

<li><a href="Durchsatz" title="Durchsatz">Durchsatz</a>: Die Anzahl beendeter Aufgaben pro Zeitspanne sollte maximiert werden. Dies ergibt eine ähnliche Strategie wie die Auslastung, betrachtet aber mehr das tatsächliche Ergebnis.</li>

<li>kurze Turnaroundzeit (<a href="Durchlaufzeit" title="Durchlaufzeit">Durchlaufzeit</a>): Die Zeit, die von der Ankunft eines Prozesses bis zu seiner vollständigen Beendigung vergeht, sollte minimiert werden.</li></ul>

<div class="mw-heading mw-heading3"><h3 id="Interaktive_Systeme_(Dialogsysteme)"><span id="Interaktive_Systeme_.28Dialogsysteme.29"></span>Interaktive Systeme (Dialogsysteme)</h3></div>

<ul><li>Niedrige Antwortzeiten: Die Wartezeiten des Benutzers (oder anderer Systeme) sollten minimiert werden. Prozesse, die eine Interaktion mit dem Benutzer erfordern, sollten also bevorzugt werden vor solchen, die im Hintergrund stattfinden können.</li>

<li>Proportionalität: Die Antwortzeiten verschiedener Prozesse sollten den Erwartungen des Benutzers entsprechen. Werden Prozesse (wie z. B. das Schließen einer <a href="Anwendungssoftware" title="Anwendungssoftware">Anwendung</a>) vom Benutzer als simpel betrachtet, sollten diese auch schnell ausgeführt werden.</li></ul>

<div class="mw-heading mw-heading3"><h3 id="Echtzeitsysteme">Echtzeitsysteme</h3></div>

<ul><li>Deadlines einhalten</li>

<li><a href="Vorhersagbarkeit" title="Vorhersagbarkeit">Vorhersagbarkeit</a>: Wichtig für <a href="Multimedia" title="Multimedia">Multimedia</a>-Anwendungen (da sonst z. B. Verschlechterung der Tonqualität droht) oder sicherheitskritische Anwendungen wie z. B. <a href="Steuerger%C3%A4t" title="Steuergerät">Steuergeräte</a> für <a href="Airbag" title="Airbag">Airbags</a>, <a href="Tempomat" class="mw-redirect" title="Tempomat">Tempomat</a> bei <a href="Kraftfahrzeug" title="Kraftfahrzeug">Kraftfahrzeugen</a> oder <a href="Autopilot" title="Autopilot">Autopiloten</a> bei <a href="Flugzeug" title="Flugzeug">Flugzeugen</a>.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Strategien">Strategien</h2></div>

<p>Das größte Problem des Schedulers ist die Tatsache, dass die benötigten <a href="Betriebsmittel_(Informatik)" title="Betriebsmittel (Informatik)">Betriebsmittel</a> für die einzelnen Prozesse nicht im Vorfeld bekannt sind. Es lässt sich also im Allgemeinen keine optimale Planung erstellen, sondern der Scheduler muss dynamisch auf geänderte Anforderungen reagieren. Dabei können (abhängig vom Scheduler) verschiedene Zuteilungsstrategien zum Einsatz kommen, u. a.:

</p>

<ul><li><b><a href="First_In_%E2%80%93_First_Out" title="First In – First Out">First In – First Out</a></b> (FIFO), <b>First-Come First-Served</b> (FCFS): Hierbei werden alle Prozesse in der Reihenfolge ihres Eingangs bearbeitet. Eine Neuzuteilung der Prozesse findet erst statt, wenn der laufende Prozess zu warten beginnt oder seine Ausführung beendet ist, das Verfahren ist daher nonpräemptive. Diese Strategie erzielt eine gute Auslastung bezüglich der CPU, allerdings nicht bezüglich Ressourcen, die längere Zeit für eine Anforderung benötigen können, wie z. B. Ein-/Ausgabe oder Massenspeicher. Für Mehrbenutzersysteme ist die Strategie darüber hinaus wenig geeignet, da einzelne Benutzer so ggf. für längere Zeit (nämlich bei aufwendigen Prozessen anderer Benutzer) ausgeschlossen werden.</li></ul>

<ul><li><b><a href="Shortest-Job-Next" title="Shortest-Job-Next">Shortest-Job-Next</a></b> (SJN), <b>Shortest Job First</b> (SJF), <b>Shortest Processing Time</b> (SPT): ein weiteres Verfahren, das nicht für Mehrbenutzersysteme geeignet ist. Es lässt sich in Fällen einsetzen, in denen die benötigte Rechenzeit für einzelne Aufgaben aus Erfahrungswerten gut vorhergesagt werden kann. Ein Nachteil ist, dass große Prozesse u. U. <i>niemals</i> die CPU zugeteilt bekommen, wenn sich immer kürzere Jobs vordrängeln. Können Prozesse unterbrochen werden, so dass ein Prozesswechsel durchgeführt wird, wenn ein neu ankommender Prozess eine kürzere Ausführungszeit aufweist als der aktuell laufende Prozess, so spricht man von <b>Shortest-Remaining-Time</b> (SRT) oder <b>Shortest-Remaining-Processing-Time</b> (SRPT).</li>

<li><a href="Lotterie-Scheduling" title="Lotterie-Scheduling"><b>Random Job Next</b></a> (RJN): Hierbei wird einem Prozess eine bestimmte Anzahl an Lotterie-Tickets zugewiesen. Der Scheduler lost ein Ticket, wonach der Prozess, welcher die Auslosung gewonnen hat, die vorgesehene Bearbeitungszeit übergeben bekommt. Der Overhead hiervon liegt bei O(2n) von der Implementation, welche nach David Petrou als <a href="Pseudocode" title="Pseudocode">Pseudocode</a> repräsentiert wird.<sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup></li></ul>

<ul><li><b>Earliest Due Date</b> (EDD): Bei dieser Strategie werden diejenigen Prozesse zuerst ausgeführt, welche die geringste <a href="Termin" title="Termin">Deadline</a> haben. Voraussetzung dafür sind statische Deadlines und gleichzeitiges Eintreffen voneinander unabhängiger Tasks. Dieses nichtunterbrechende Verfahren ist ideal, um die maximale Verspätung zu minimieren. Wenn Prozesse unterbrochen werden können spricht man von einer <b>Terminabhängigen Ablaufplanung</b>, <b>Planen nach Fristen</b> oder <b><a href="Earliest_Deadline_First" title="Earliest Deadline First">Earliest Deadline First</a></b> (EDF). Diese Strategie kommt hauptsächlich in Echtzeitsystemen vor, da es damit möglich ist, eine definierte Antwortzeit für bestimmte Prozesse zu garantieren.</li></ul>

<ul><li><b><a href="Priorit%C3%A4tsscheduling" title="Prioritätsscheduling">Prioritätsscheduling</a></b>: Bei dieser Strategie wird jedem Prozess eine Priorität zugeordnet. Die Abarbeitung erfolgt dann in der Reihenfolge der Prioritäten.

<ul><li><b><a href="Rate_Monotonic_Scheduling" title="Rate Monotonic Scheduling">Rate Monotonic Scheduling</a></b> (RMS): Die Priorität wird aus der Periodenlänge berechnet (Prozesse mit kürzeren Perioden haben höhere Priorität).</li>

<li><b><a href="Deadline_Monotonic_Scheduling" title="Deadline Monotonic Scheduling">Deadline Monotonic Scheduling</a></b> (DMS): Die Priorität wird aus der relativen Deadline berechnet (Prozesse mit kürzeren relativen Deadlines haben höhere Priorität).</li>

<li>Man kann auch mehreren Prozessen die gleiche Priorität geben, sie werden dann in Eingangsreihenfolge ausgeführt, oder mit einem untergeordneten Zeitscheibenverfahren innerhalb der gleichen Priorität abgewechselt (zum Beispiel <b><a href="Multilevel_Feedback_Queue" title="Multilevel Feedback Queue">Multilevel Feedback Queue</a> Scheduling</b> oder <b>Shortest-Elapsed-Time</b> (SET) )</li>

<li>Die Prioritäten können auch dynamisch sein, wobei sich die Priorität eines Prozesses mit der Zeit erhöht, damit auch niedrig priorisierte Prozesse irgendwann bearbeitet werden und nicht ständig von höher priorisierten Prozessen verdrängt werden.</li></ul></li></ul>

<ul><li><b><a href="Round_Robin_(Informatik)" title="Round Robin (Informatik)">Round Robin</a></b>, <b>Zeitscheibenverfahren</b>: Einem Prozess wird die CPU für eine bestimmte (kurze) Zeitspanne zugeteilt. Danach wird der Prozess wieder hinten in die Warteschlange eingereiht. Sind die einzelnen Zeitspannen unterschiedlich groß, so spricht man von Weighted Round Robin (WRR)</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Scheduling-Verfahren">Scheduling-Verfahren</h2></div>

<ul><li><a href="Completely_Fair_Scheduler" title="Completely Fair Scheduler">Completely Fair Scheduler</a> (CFS), Scheduler von <a href="Linux" title="Linux">Linux</a> von 2.6.23 bis 6.6</li>

<li><a href="Fair-Share-Scheduling" title="Fair-Share-Scheduling">Fair-Share-Scheduling</a></li>

<li><a href="Brain_Fuck_Scheduler" title="Brain Fuck Scheduler">Brain Fuck Scheduler</a></li>

<li><a href="Highest_Response_Ratio_Next" title="Highest Response Ratio Next">Highest Response Ratio Next</a> (HRRN)</li>

<li><a href="Least_Laxity_First" title="Least Laxity First">Least Laxity First</a> (Planen nach Spielraum)</li>

<li><a href="Lotterie-Scheduling" title="Lotterie-Scheduling">Lotterie-Scheduling</a></li>

<li><a href="Three-Level-Scheduling" title="Three-Level-Scheduling">Three-Level-Scheduling</a></li>

<li><i>Credit Scheduler</i><sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup>, <i>Credit2 Scheduler</i><sup id="cite_ref-4" class="reference"><a href="#cite_note-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup> von <a href="Xen" title="Xen">Xen</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Literatur">Literatur</h2></div>

<ul><li><a href="Andrew_S._Tanenbaum" title="Andrew S. Tanenbaum">Tanenbaum, Andrew S.</a>: <i>Moderne Betriebssysteme</i> ISBN 3-8273-7019-1</li>

<li>A. Silberschatz, P. B. Galvin, G. Gagne: <i>Operating System Concepts</i>, 7th edition, John Wiley & Sons Inc. 2000, ISBN 0-471-69466-5</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Einzelnachweise">Einzelnachweise</h2></div>

<li id="cite_note-1"><span class="mw-cite-backlink"><a href="#cite_ref-1">↑</a></span> <span class="reference-text"><a href="Otto_Spaniol" title="Otto Spaniol">Otto Spaniol</a>: <i>Systemprogrammierung : Skript zur Vorlesung an der RWTH Aachen.</i> 1996, ISBN 3-86073-470-9</span>

</li>

<li id="cite_note-2"><span class="mw-cite-backlink"><a href="#cite_ref-2">↑</a></span> <span class="reference-text"><span class="cite">David Petrou, John W. Milford, Garth A. Gibson: <a rel="nofollow" class="external text" href="https://www.usenix.org/legacy/events/usenix99/full_papers/petrou/petrou.pdf"><i>Implementing Lottery Scheduling: Matching the Specializations in Traditional Schedulers.</i></a> (PDF) In: <i>USENIX.</i> USENIX Annual Technical Conference, 6. Juni 1999,<span class="Abrufdatum"> abgerufen am 8. November 2021</span> (englisch).</span><span style="display: none;" class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Adc&rfr_id=info%3Asid%2Fde.wikipedia.org%3AProzess-Scheduler&rft.title=Implementing+Lottery+Scheduling%3A+Matching+the+Specializations+in+Traditional+Schedulers&rft.description=Implementing+Lottery+Scheduling%3A+Matching+the+Specializations+in+Traditional+Schedulers&rft.identifier=https%3A%2F%2Fwww.usenix.org%2Flegacy%2Fevents%2Fusenix99%2Ffull_papers%2Fpetrou%2Fpetrou.pdf&rft.creator=David+Petrou%2C+John+W.+Milford%2C+Garth+A.+Gibson&rft.publisher=USENIX+Annual+Technical+Conference&rft.date=1999-06-06&rft.language=en"> </span></span>

</li>

<li id="cite_note-3"><span class="mw-cite-backlink"><a href="#cite_ref-3">↑</a></span> <span class="reference-text"><a rel="nofollow" class="external text" href="https://wiki.xenproject.org/wiki/Credit_Scheduler">Credit Scheduler</a> im <a rel="nofollow" class="external text" href="https://wiki.xenproject.org/wiki/Main_Page">Xen-Wiki</a></span>

</li>

<li id="cite_note-4"><span class="mw-cite-backlink"><a href="#cite_ref-4">↑</a></span> <span class="reference-text"><a rel="nofollow" class="external text" href="https://wiki.xenproject.org/wiki/Credit2_Scheduler">Credit2 Scheduler</a> im <a rel="nofollow" class="external text" href="https://wiki.xenproject.org/wiki/Main_Page">Xen-Wiki</a></span>

</li>

</ol></div><div><div class="zim-footer">

Dieser Artikel wurde von <a class="external text" title="Zuletzt bearbeitet am 2024-12-29" href="https://de.wikipedia.org/wiki/?title=Prozess-Scheduler&oldid=251680761">Wikipedia</a> herausgegeben. Der Text ist unter <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.de">Creative Commons Attribution-Share Alike 4.0</a> verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.

</div>

</div></div>

</div>

</main>

</div>

</body></html>